package com.algorithmic.sort;

import java.util.List;

/**
 * @author: zhangxupeng
 * @date:2019/6/26
 * @Email: 1452806452@qq.com
 * 插入排序
 **/
public class InsertionSort {
    /**
     * 插入排序
     * 时间复杂度O(N)
     * 局部有序的话特别快
     *
     * @param list
     */
    public static void insertionSort(List<Integer> list) {
        for (int out = 1; out < list.size(); out++) {
            int temp = list.get(out);
            int in = out;
            while (in > 0 && list.get(in - 1) > temp) {
                list.set(in, list.get(in - 1));
                --in;
            }
            list.set(in, temp);
        }
    }
}
